<?php

class Solution{

    function test($commands,$params){

        $result=[];

        foreach($commands as $k=>$command){
            $param=$params[$k];

            switch($command){
                case 'LRUCache':
                    $obj=new LRUCache(...$param);
                    $result[]=null;
                    break;
                case 'put':
                    $obj->put(...$param);
                    $result[]=null;
                    break;
                case 'get':
                    $result[]=$obj->get(...$param);
                    break;
            }
        }

        return $result;
    }

    function debug(){
        return $this->test(
            ["LRUCache","get","put","get","put","put","get","get"],
            [[2],[2],[2,6],[1],[1,5],[1,2],[1],[2]]
        );
    }
}

/**
 * Class LRUCache
 */
class LRUCache {

    protected $capacity;

    protected $data=[];

    protected $sortKeys=[];//最近使用的key排序，下标值越大为最近使用的

    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->capacity=$capacity;
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {

        if(!array_key_exists($key,$this->data)){
            return -1;
        }
        $this->setKeyTop($key);

        $a=$this->data[$key];
        return $a;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {

        //key存在的直接替换，并修改最近使用的key排序
        if(array_key_exists($key,$this->data)){
            $this->data[$key]=$value;
            $this->setKeyTop($key);
            return;
        }

        //缓存容量未达上限，则直接加入
        if(sizeof($this->sortKeys)<$this->capacity){
            $this->data[$key]=$value;
            $this->sortKeys[]=$key;
            return;
        }

        //缓存容量达到上限，删除最少使用的key，
        unset($this->data[$this->sortKeys[0]]);
        unset($this->sortKeys[0]);
        $this->sortKeys=array_values($this->sortKeys);

        $this->data[$key]=$value;
        $this->sortKeys[]=$key;

    }

    /**
     * 设置key最大值
     * @param $key
     */
    function setKeyTop($key){
        foreach($this->sortKeys as $i=>$k){
            if($k==$key){
                unset($this->sortKeys[$i]);
                $this->sortKeys=array_values($this->sortKeys);
                break;
            }
        }
        $this->sortKeys[]=$key;
    }
}
